import java.util.*;

/**
 * @author doreaxon
 * @version 1.0
 * @date 2024/8/11 23:07
 * @注释
 *
 * 3. 无重复字符的最长子串
 * 中等
 * 相关标签
 * 相关企业
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长
 * 子串
 *  的长度。
 *
 *
 *
 * 示例 1:
 *
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 *
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 *
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *
 *
 * 提示：
 *
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 */
public class LengthOfLongestSubstring {
    //自己做的版本 （没做出来0）
    public static int lengthOfLongestSubstring(String s) {
        if (s.length() == 0){
            return 0;
        }
        HashMap<String, Integer> hashMap = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        String str = "";
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            str += c;
            if (hashMap.containsKey(c+"")){
                list.add(str.length() - 1 == 0 ? 1 : str.length() - 1) ;
                i = hashMap.get("" + c) + 1;
                hashMap.remove(c+"");

                str = c+"";
            }else {
                list.add(str.length());
                hashMap.put(c+"",i);
            }

        }
        Collections.sort(list);
        return list.get(list.size() - 1);
    }

    //pwwkew  abcabcbb
    public static int lengthOfLongestSubstring2(String s) {
        if (s.length() == 0){
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int length = 1;
        for (int i = 0 ,j = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)){
                //之前的是: j = map.get(c) + 1;
                // 当遇到重复字符时，简单地将 j 设置为 map.get(c) + 1 可能会导致跳过更长的潜在子串。如abba
                j = Math.max(j,map.get(c) + 1);
            }
            map.put(c,i);
            length = Math.max(length, i - j + 1);


        }
        return length;

    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring2("abba"));
    }
}
